home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / gems / g_gemsi.lha / GraphicsGems / PolyScan / poly_clip.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-04-10  |  4.0 KB  |  133 lines
  1.  
  2.  
  3. /*
  4.  * poly_clip.c: homogeneous 3-D convex polygon clipper
  5.  *
  6.  * Paul Heckbert    1985, Dec 1989
  7.  */
  8.  
  9. #include "poly.h"
  10.  
  11. #define SWAP(a, b, temp)    {temp = a; a = b; b = temp;}
  12. #define COORD(vert, i)  ((double *)(vert))[i]
  13.  
  14. #define CLIP_AND_SWAP(elem, sign, k, p, q, r) { \
  15.     poly_clip_to_halfspace(p, q, &v->elem-(double *)v, sign, sign*k); \
  16.     if (q->n==0) {p1->n = 0; return POLY_CLIP_OUT;} \
  17.     SWAP(p, q, r); \
  18. }
  19.  
  20.  
  21. /*
  22.  * poly_clip_to_box: Clip the convex polygon p1 to the screen space box
  23.  * using the homogeneous screen coordinates (sx, sy, sz, sw) of each              
  24.  * vertex, testing if v->sx/v->sw > box->x0 and v->sx/v->sw < box->x1, 
  25.  * and similar tests for y and z, for each vertex v of the polygon.
  26.  * If polygon is entirely inside box, then POLY_CLIP_IN is returned.
  27.  * If polygon is entirely outside box, then POLY_CLIP_OUT is returned.
  28.  * Otherwise, if the polygon is cut by the box, p1 is modified and
  29.  * POLY_CLIP_PARTIAL is returned.
  30.  */
  31.  
  32. int poly_clip_to_box(p1, box)
  33. register Poly *p1;
  34. register Poly_box *box;
  35. {
  36.     int x0out = 0, x1out = 0, y0out = 0, y1out = 0, z0out = 0, 
  37.         z1out = 0;
  38.     register int i;
  39.     register Poly_vert *v;
  40.     Poly p2, *p, *q, *r;
  41.  
  42.     /* count vertices "outside" with respect to each */
  43.     /* of the six planes */
  44.     for (v=p1->vert, i=p1->n; i>0; i--, v++) {
  45.         if (v->sx < box->x0*v->sw) x0out++;    /* out on left */
  46.         if (v->sx > box->x1*v->sw) x1out++;    /* out on right */
  47.         if (v->sy < box->y0*v->sw) y0out++;    /* out on top */
  48.         if (v->sy > box->y1*v->sw) y1out++;    /* out on bottom */
  49.         if (v->sz < box->z0*v->sw) z0out++;    /* out on near */
  50.         if (v->sz > box->z1*v->sw) z1out++;    /* out on far */
  51.     }
  52.  
  53.     /* check if all vertices inside */
  54.     if (x0out+x1out+y0out+y1out+z0out+z1out == 0) return POLY_CLIP_IN;
  55.  
  56.     /* check if all vertices are "outside" any of the six planes */
  57.     if (x0out==p1->n || x1out==p1->n || y0out==p1->n ||
  58.         y1out==p1->n || z0out==p1->n || z1out==p1->n) {
  59.         p1->n = 0;
  60.         return POLY_CLIP_OUT;
  61.     }
  62.  
  63.  
  64.     /*
  65.      * now clip against each of the planes that might cut the polygon,
  66.      * at each step toggling between polygons p1 and p2
  67.      */
  68.     p = p1;
  69.     q = &p2;
  70.     if (x0out) CLIP_AND_SWAP(sx, -1., box->x0, p, q, r);
  71.     if (x1out) CLIP_AND_SWAP(sx,  1., box->x1, p, q, r);
  72.     if (y0out) CLIP_AND_SWAP(sy, -1., box->y0, p, q, r);
  73.     if (y1out) CLIP_AND_SWAP(sy,  1., box->y1, p, q, r);
  74.     if (z0out) CLIP_AND_SWAP(sz, -1., box->z0, p, q, r);
  75.     if (z1out) CLIP_AND_SWAP(sz,  1., box->z1, p, q, r);
  76.  
  77.     /* if result ended up in p2 then copy it to p1 */
  78.     if (p==&p2)
  79.         bcopy(&p2, p1, sizeof(Poly)-
  80.             (POLY_NMAX-p2.n)*sizeof(Poly_vert));
  81.     return POLY_CLIP_PARTIAL;
  82. }
  83.  
  84. /*
  85.  * poly_clip_to_halfspace: clip convex polygon p against a plane,
  86.  * copying the portion satisfying sign*s[index] < k*sw into q,
  87.  * where s is a Poly_vert* cast as a double*.
  88.  * index is an index into the array of doubles at each vertex, such that
  89.  * s[index] is sx, sy, or sz (screen space x, y, or z).
  90.  * Thus, to clip against xmin, use
  91.  *    poly_clip_to_halfspace(p, q, XINDEX, -1., -xmin);
  92.  * and to clip against xmax, use
  93.  *    poly_clip_to_halfspace(p, q, XINDEX,  1.,  xmax);
  94.  */
  95.  
  96. void poly_clip_to_halfspace(p, q, index, sign, k)
  97. Poly *p, *q;
  98. register int index;
  99. double sign, k;
  100. {
  101.     register int m;
  102.     register double *up, *vp, *wp;
  103.     register Poly_vert *v;
  104.     int i;
  105.     Poly_vert *u;
  106.     double t, tu, tv;
  107.  
  108.     q->n = 0;
  109.     q->mask = p->mask;
  110.  
  111.  
  112.     /* start with u=vert[n-1], v=vert[0] */
  113.     u = &p->vert[p->n-1];
  114.     tu = sign*COORD(u, index) - u->sw*k;
  115.     for (v= &p->vert[0], i=p->n; i>0; i--, u=v, tu=tv, v++) {
  116.     /* on old polygon (p), u is previous vertex, v is current vertex */
  117.     /* tv is negative if vertex v is in */
  118.         tv = sign*COORD(v, index) - v->sw*k;
  119.         if (tu<=0. ^ tv<=0.) {
  120.             /* edge crosses plane; add intersection point to q */
  121.             t = tu/(tu-tv);
  122.             vp = (double *)v;
  123.             wp = (double *)&q->vert[q->n];
  124.             for (m=p->mask; m!=0; m>>=1, up++, vp++, wp++)
  125.                 if (m&1) *wp = *up+t*(*vp-*up);
  126.             q->n++;
  127.         }
  128.         if (tv<=0.)        /* vertex v is in, copy it to q */
  129.             q->vert[q->n++] = *v;
  130.     }
  131. }
  132.  
  133.